#include <stdio.h>//ok
#include <tchar.h>//ok
#include <stdlib.h>//ok

typedef unsigned char uint8_t;
typedef short int16_t;
typedef unsigned short uint16_t;
typedef unsigned long long uint64_t;
typedef long long int64_t;
typedef int16_t coeff_t;

enum JpegReadMode {
	JPEG_READ_HEADER,   // only basic headers
	JPEG_READ_TABLES,   // headers and tables (quant, Huffman, ...)
	JPEG_READ_ALL,      // everything
};

enum JPEGReadError {
	JPEG_OK = 0,
	JPEG_SOI_NOT_FOUND,
	JPEG_SOF_NOT_FOUND,
	JPEG_UNEXPECTED_EOF,
	JPEG_MARKER_BYTE_NOT_FOUND,
	JPEG_UNSUPPORTED_MARKER,
	JPEG_WRONG_MARKER_SIZE,
	JPEG_INVALID_PRECISION,
	JPEG_INVALID_WIDTH,
	JPEG_INVALID_HEIGHT,
	JPEG_INVALID_NUMCOMP,
	JPEG_INVALID_SAMP_FACTOR,
	JPEG_INVALID_START_OF_SCAN,
	JPEG_INVALID_END_OF_SCAN,
	JPEG_INVALID_SCAN_BIT_POSITION,
	JPEG_INVALID_COMPS_IN_SCAN,
	JPEG_INVALID_HUFFMAN_INDEX,
	JPEG_INVALID_QUANT_TBL_INDEX,
	JPEG_INVALID_QUANT_VAL,
	JPEG_INVALID_MARKER_LEN,
	JPEG_INVALID_SAMPLING_FACTORS,
	JPEG_INVALID_HUFFMAN_CODE,
	JPEG_INVALID_SYMBOL,
	JPEG_NON_REPRESENTABLE_DC_COEFF,
	JPEG_NON_REPRESENTABLE_AC_COEFF,
	JPEG_INVALID_SCAN,
	JPEG_OVERLAPPING_SCANS,
	JPEG_INVALID_SCAN_ORDER,
	JPEG_EXTRA_ZERO_RUN,
	JPEG_DUPLICATE_DRI,
	JPEG_DUPLICATE_SOF,
	JPEG_WRONG_RESTART_MARKER,
	JPEG_DUPLICATE_COMPONENT_ID,
	JPEG_COMPONENT_NOT_FOUND,
	JPEG_HUFFMAN_TABLE_NOT_FOUND,
	JPEG_HUFFMAN_TABLE_ERROR,
	JPEG_QUANT_TABLE_NOT_FOUND,
	JPEG_EMPTY_DHT,
	JPEG_EMPTY_DQT,
	JPEG_OUT_OF_BAND_COEFF,
	JPEG_EOB_RUN_TOO_LONG,
	JPEG_IMAGE_TOO_LARGE,
};


static const int kJpegHuffmanRootTableBits = 8;
// Maximum huffman lookup table size.
// According to zlib/examples/enough.c, 758 entries are always enough for
// an alphabet of 257 symbols (256 + 1 special symbol for the all 1s code) and
// max bit length 16 if the root table has 8 bits.
static const int kJpegHuffmanLutSize = 758;

struct HuffmanTableEntry {
	// Initialize the value to an invalid symbol so that we can recognize it
	// when reading the bit stream using a Huffman code with space > 0.

	uint8_t bits;     // number of bits used for this symbol
	uint16_t value;   // symbol value or table offset
};
void initHuffmanTableEntry(HuffmanTableEntry* obj){
	obj->bits = 0;
	obj->value = 0xffff;
}

static const int kDCTBlockSize = 64;
static const int kMaxComponents = 4;
static const int kMaxQuantTables = 4;
static const int kMaxHuffmanTables = 4;
static const int kJpegHuffmanMaxBitLength = 16;
static const int kJpegHuffmanAlphabetSize = 256;
static const int kJpegDCAlphabetSize = 12;
static const int kMaxDHTMarkers = 512;

static const uint8_t kDefaultQuantMatrix[2][64] = {
	{ 16, 11, 10, 16, 24, 40, 51, 61,
	12, 12, 14, 19, 26, 58, 60, 55,
	14, 13, 16, 24, 40, 57, 69, 56,
	14, 17, 22, 29, 51, 87, 80, 62,
	18, 22, 37, 56, 68, 109, 103, 77,
	24, 35, 55, 64, 81, 104, 113, 92,
	49, 64, 78, 87, 103, 121, 120, 101,
	72, 92, 95, 98, 112, 100, 103, 99 },
	{ 17, 18, 24, 47, 99, 99, 99, 99,
	18, 21, 26, 66, 99, 99, 99, 99,
	24, 26, 56, 99, 99, 99, 99, 99,
	47, 66, 99, 99, 99, 99, 99, 99,
	99, 99, 99, 99, 99, 99, 99, 99,
	99, 99, 99, 99, 99, 99, 99, 99,
	99, 99, 99, 99, 99, 99, 99, 99,
	99, 99, 99, 99, 99, 99, 99, 99 }
};

const int kJPEGNaturalOrder[80] = {
	0, 1, 8, 16, 9, 2, 3, 10,
	17, 24, 32, 25, 18, 11, 4, 5,
	12, 19, 26, 33, 40, 48, 41, 34,
	27, 20, 13, 6, 7, 14, 21, 28,
	35, 42, 49, 56, 57, 50, 43, 36,
	29, 22, 15, 23, 30, 37, 44, 51,
	58, 59, 52, 45, 38, 31, 39, 46,
	53, 60, 61, 54, 47, 55, 62, 63,
	// extra entries for safety in decoder
	63, 63, 63, 63, 63, 63, 63, 63,
	63, 63, 63, 63, 63, 63, 63, 63
};

const int kJPEGZigZagOrder[64] = {
	0, 1, 5, 6, 14, 15, 27, 28,
	2, 4, 7, 13, 16, 26, 29, 42,
	3, 8, 12, 17, 25, 30, 41, 43,
	9, 11, 18, 24, 31, 40, 44, 53,
	10, 19, 23, 32, 39, 45, 52, 54,
	20, 22, 33, 38, 46, 51, 55, 60,
	21, 34, 37, 47, 50, 56, 59, 61,
	35, 36, 48, 49, 57, 58, 62, 63
};

// Quantization values for an 8x8 pixel block.
struct JPEGQuantTable {
	int* values;
	//int precision;
	// The index of this quantization table as it was parsed from the input JPEG.
	// Each DQT marker segment contains an 'index' field, and we save this index
	// here. Valid values are 0 to 3.
	int index;
	// Set to true if this table is the last one within its marker segment.
	//bool is_last;
};

void initJPEGQuantTable(JPEGQuantTable* obj){
	//obj->precision = 0;
	obj->index = 0;
	//obj->is_last = true;
}

// Huffman table indexes used for one component of one scan.
struct JPEGComponentScanInfo {
	int comp_idx;
	int dc_tbl_idx;
	int ac_tbl_idx;
};

// Contains information that is used in one scan.
struct JPEGScanInfo {
	// Parameters used for progressive scans (named the same way as in the spec):
	//   Ss : Start of spectral band in zig-zag sequence.
	//   Se : End of spectral band in zig-zag sequence.
	//   Ah : Successive approximation bit position, high.
	//   Al : Successive approximation bit position, low.
	int Ss;
	int Se;
	int Ah;
	int Al;
	JPEGComponentScanInfo* components;
	int componentsLen;
};

// Represents one component of a jpeg file.
struct JPEGComponent {

	// One-byte id of the component.
	int id;
	// Horizontal and vertical sampling factors.
	// In interleaved mode, each minimal coded unit (MCU) has
	// h_samp_factor x v_samp_factor DCT blocks from this component.
	int h_samp_factor;
	int v_samp_factor;
	// The index of the quantization table used for this component.
	int quant_idx;
	// The dimensions of the component measured in 8x8 blocks.
	int width_in_blocks;
	int height_in_blocks;
	int num_blocks;
	// The DCT coefficients of this component, laid out block-by-block, divided
	// through the quantization matrix values.
	coeff_t* coeffs;
	int coeffsLen;
};

void initJPEGComponent(JPEGComponent* obj){
	obj->id = 0;
	obj->h_samp_factor = 1;
	obj->v_samp_factor = 1;
	obj->quant_idx = 0;
	obj->width_in_blocks = 0;
	obj->height_in_blocks = 0;
}

struct myVector {
	void* p;
	myVector* next;
};

struct mystr {
	const uint8_t* str;
	int len;
};

// Represents a parsed jpeg file.
struct JPEGData {
	//bool Is420() const;
	//bool Is444() const;
	bool Is420() const {
		return (componentsLen == 3 &&
			max_h_samp_factor == 2 &&
			max_v_samp_factor == 2 &&
			components[0].h_samp_factor == 2 &&
			components[0].v_samp_factor == 2 &&
			components[1].h_samp_factor == 1 &&
			components[1].v_samp_factor == 1 &&
			components[2].h_samp_factor == 1 &&
			components[2].v_samp_factor == 1);
	}

	bool Is444() const {
		return (componentsLen == 3 &&
			max_h_samp_factor == 1 &&
			max_v_samp_factor == 1 &&
			components[0].h_samp_factor == 1 &&
			components[0].v_samp_factor == 1 &&
			components[1].h_samp_factor == 1 &&
			components[1].v_samp_factor == 1 &&
			components[2].h_samp_factor == 1 &&
			components[2].v_samp_factor == 1);
	}

	int width;
	int height;
	int version;
	int max_h_samp_factor;
	int max_v_samp_factor;
	int MCU_rows;
	int MCU_cols;
	int restart_interval;
	myVector* app_data;// mystr
	myVector* quant;//JPEGQuantTable
	int quantLen;
	myVector* huffman_code;//int slot_id TODO not needed only for check
	int huffman_codeLen;
	JPEGComponent* components;
	int componentsLen;
	JPEGScanInfo scan_info;
	const uint8_t* tail_data;//std::string
	const uint8_t* original_jpg;
	size_t original_jpg_size;
	JPEGReadError error;
};
void initJPEGData(JPEGData* obj){
	obj->width = (0);
	obj->height = (0);
	obj->version = (0);
	obj->max_h_samp_factor = (1);
	obj->max_v_samp_factor = (1);
	obj->MCU_rows = (0);
	obj->MCU_cols = (0);
	obj->restart_interval = (0);
	obj->original_jpg = (NULL);
	obj->original_jpg_size = (0);
	obj->app_data = (0);
	obj->quant = (0);
	obj->quantLen = (0);
	obj->huffman_code = (0);
	obj->huffman_codeLen = (0);
	obj->error = (JPEG_OK);
}


static const int kCrToRedTable[256] = {
	-179, -178, -177, -175, -174, -172, -171, -170, -168, -167, -165, -164,
	-163, -161, -160, -158, -157, -156, -154, -153, -151, -150, -149, -147,
	-146, -144, -143, -142, -140, -139, -137, -136, -135, -133, -132, -130,
	-129, -128, -126, -125, -123, -122, -121, -119, -118, -116, -115, -114,
	-112, -111, -109, -108, -107, -105, -104, -102, -101, -100, -98, -97,
	-95, -94, -93, -91, -90, -88, -87, -86, -84, -83, -81, -80,
	-79, -77, -76, -74, -73, -72, -70, -69, -67, -66, -64, -63,
	-62, -60, -59, -57, -56, -55, -53, -52, -50, -49, -48, -46,
	-45, -43, -42, -41, -39, -38, -36, -35, -34, -32, -31, -29,
	-28, -27, -25, -24, -22, -21, -20, -18, -17, -15, -14, -13,
	-11, -10, -8, -7, -6, -4, -3, -1, 0, 1, 3, 4,
	6, 7, 8, 10, 11, 13, 14, 15, 17, 18, 20, 21,
	22, 24, 25, 27, 28, 29, 31, 32, 34, 35, 36, 38,
	39, 41, 42, 43, 45, 46, 48, 49, 50, 52, 53, 55,
	56, 57, 59, 60, 62, 63, 64, 66, 67, 69, 70, 72,
	73, 74, 76, 77, 79, 80, 81, 83, 84, 86, 87, 88,
	90, 91, 93, 94, 95, 97, 98, 100, 101, 102, 104, 105,
	107, 108, 109, 111, 112, 114, 115, 116, 118, 119, 121, 122,
	123, 125, 126, 128, 129, 130, 132, 133, 135, 136, 137, 139,
	140, 142, 143, 144, 146, 147, 149, 150, 151, 153, 154, 156,
	157, 158, 160, 161, 163, 164, 165, 167, 168, 170, 171, 172,
	174, 175, 177, 178
};

static const int kCbToBlueTable[256] = {
	-227, -225, -223, -222, -220, -218, -216, -214, -213, -211, -209, -207,
	-206, -204, -202, -200, -198, -197, -195, -193, -191, -190, -188, -186,
	-184, -183, -181, -179, -177, -175, -174, -172, -170, -168, -167, -165,
	-163, -161, -159, -158, -156, -154, -152, -151, -149, -147, -145, -144,
	-142, -140, -138, -136, -135, -133, -131, -129, -128, -126, -124, -122,
	-120, -119, -117, -115, -113, -112, -110, -108, -106, -105, -103, -101,
	-99, -97, -96, -94, -92, -90, -89, -87, -85, -83, -82, -80,
	-78, -76, -74, -73, -71, -69, -67, -66, -64, -62, -60, -58,
	-57, -55, -53, -51, -50, -48, -46, -44, -43, -41, -39, -37,
	-35, -34, -32, -30, -28, -27, -25, -23, -21, -19, -18, -16,
	-14, -12, -11, -9, -7, -5, -4, -2, 0, 2, 4, 5,
	7, 9, 11, 12, 14, 16, 18, 19, 21, 23, 25, 27,
	28, 30, 32, 34, 35, 37, 39, 41, 43, 44, 46, 48,
	50, 51, 53, 55, 57, 58, 60, 62, 64, 66, 67, 69,
	71, 73, 74, 76, 78, 80, 82, 83, 85, 87, 89, 90,
	92, 94, 96, 97, 99, 101, 103, 105, 106, 108, 110, 112,
	113, 115, 117, 119, 120, 122, 124, 126, 128, 129, 131, 133,
	135, 136, 138, 140, 142, 144, 145, 147, 149, 151, 152, 154,
	156, 158, 159, 161, 163, 165, 167, 168, 170, 172, 174, 175,
	177, 179, 181, 183, 184, 186, 188, 190, 191, 193, 195, 197,
	198, 200, 202, 204, 206, 207, 209, 211, 213, 214, 216, 218,
	220, 222, 223, 225,
};

static const int kCrToGreenTable[256] = {
	5990656, 5943854, 5897052, 5850250, 5803448, 5756646, 5709844, 5663042,
	5616240, 5569438, 5522636, 5475834, 5429032, 5382230, 5335428, 5288626,
	5241824, 5195022, 5148220, 5101418, 5054616, 5007814, 4961012, 4914210,
	4867408, 4820606, 4773804, 4727002, 4680200, 4633398, 4586596, 4539794,
	4492992, 4446190, 4399388, 4352586, 4305784, 4258982, 4212180, 4165378,
	4118576, 4071774, 4024972, 3978170, 3931368, 3884566, 3837764, 3790962,
	3744160, 3697358, 3650556, 3603754, 3556952, 3510150, 3463348, 3416546,
	3369744, 3322942, 3276140, 3229338, 3182536, 3135734, 3088932, 3042130,
	2995328, 2948526, 2901724, 2854922, 2808120, 2761318, 2714516, 2667714,
	2620912, 2574110, 2527308, 2480506, 2433704, 2386902, 2340100, 2293298,
	2246496, 2199694, 2152892, 2106090, 2059288, 2012486, 1965684, 1918882,
	1872080, 1825278, 1778476, 1731674, 1684872, 1638070, 1591268, 1544466,
	1497664, 1450862, 1404060, 1357258, 1310456, 1263654, 1216852, 1170050,
	1123248, 1076446, 1029644, 982842, 936040, 889238, 842436, 795634,
	748832, 702030, 655228, 608426, 561624, 514822, 468020, 421218,
	374416, 327614, 280812, 234010, 187208, 140406, 93604, 46802,
	0, -46802, -93604, -140406, -187208, -234010, -280812, -327614,
	-374416, -421218, -468020, -514822, -561624, -608426, -655228, -702030,
	-748832, -795634, -842436, -889238, -936040, -982842, -1029644, -1076446,
	-1123248, -1170050, -1216852, -1263654, -1310456, -1357258, -1404060, -1450862,
	-1497664, -1544466, -1591268, -1638070, -1684872, -1731674, -1778476, -1825278,
	-1872080, -1918882, -1965684, -2012486, -2059288, -2106090, -2152892, -2199694,
	-2246496, -2293298, -2340100, -2386902, -2433704, -2480506, -2527308, -2574110,
	-2620912, -2667714, -2714516, -2761318, -2808120, -2854922, -2901724, -2948526,
	-2995328, -3042130, -3088932, -3135734, -3182536, -3229338, -3276140, -3322942,
	-3369744, -3416546, -3463348, -3510150, -3556952, -3603754, -3650556, -3697358,
	-3744160, -3790962, -3837764, -3884566, -3931368, -3978170, -4024972, -4071774,
	-4118576, -4165378, -4212180, -4258982, -4305784, -4352586, -4399388, -4446190,
	-4492992, -4539794, -4586596, -4633398, -4680200, -4727002, -4773804, -4820606,
	-4867408, -4914210, -4961012, -5007814, -5054616, -5101418, -5148220, -5195022,
	-5241824, -5288626, -5335428, -5382230, -5429032, -5475834, -5522636, -5569438,
	-5616240, -5663042, -5709844, -5756646, -5803448, -5850250, -5897052, -5943854,
};

static const int kCbToGreenTable[256] = {
	2919680, 2897126, 2874572, 2852018, 2829464, 2806910, 2784356, 2761802,
	2739248, 2716694, 2694140, 2671586, 2649032, 2626478, 2603924, 2581370,
	2558816, 2536262, 2513708, 2491154, 2468600, 2446046, 2423492, 2400938,
	2378384, 2355830, 2333276, 2310722, 2288168, 2265614, 2243060, 2220506,
	2197952, 2175398, 2152844, 2130290, 2107736, 2085182, 2062628, 2040074,
	2017520, 1994966, 1972412, 1949858, 1927304, 1904750, 1882196, 1859642,
	1837088, 1814534, 1791980, 1769426, 1746872, 1724318, 1701764, 1679210,
	1656656, 1634102, 1611548, 1588994, 1566440, 1543886, 1521332, 1498778,
	1476224, 1453670, 1431116, 1408562, 1386008, 1363454, 1340900, 1318346,
	1295792, 1273238, 1250684, 1228130, 1205576, 1183022, 1160468, 1137914,
	1115360, 1092806, 1070252, 1047698, 1025144, 1002590, 980036, 957482,
	934928, 912374, 889820, 867266, 844712, 822158, 799604, 777050,
	754496, 731942, 709388, 686834, 664280, 641726, 619172, 596618,
	574064, 551510, 528956, 506402, 483848, 461294, 438740, 416186,
	393632, 371078, 348524, 325970, 303416, 280862, 258308, 235754,
	213200, 190646, 168092, 145538, 122984, 100430, 77876, 55322,
	32768, 10214, -12340, -34894, -57448, -80002, -102556, -125110,
	-147664, -170218, -192772, -215326, -237880, -260434, -282988, -305542,
	-328096, -350650, -373204, -395758, -418312, -440866, -463420, -485974,
	-508528, -531082, -553636, -576190, -598744, -621298, -643852, -666406,
	-688960, -711514, -734068, -756622, -779176, -801730, -824284, -846838,
	-869392, -891946, -914500, -937054, -959608, -982162, -1004716, -1027270,
	-1049824, -1072378, -1094932, -1117486, -1140040, -1162594, -1185148, -1207702,
	-1230256, -1252810, -1275364, -1297918, -1320472, -1343026, -1365580, -1388134,
	-1410688, -1433242, -1455796, -1478350, -1500904, -1523458, -1546012, -1568566,
	-1591120, -1613674, -1636228, -1658782, -1681336, -1703890, -1726444, -1748998,
	-1771552, -1794106, -1816660, -1839214, -1861768, -1884322, -1906876, -1929430,
	-1951984, -1974538, -1997092, -2019646, -2042200, -2064754, -2087308, -2109862,
	-2132416, -2154970, -2177524, -2200078, -2222632, -2245186, -2267740, -2290294,
	-2312848, -2335402, -2357956, -2380510, -2403064, -2425618, -2448172, -2470726,
	-2493280, -2515834, -2538388, -2560942, -2583496, -2606050, -2628604, -2651158,
	-2673712, -2696266, -2718820, -2741374, -2763928, -2786482, -2809036, -2831590,
};

static const uint8_t kRangeLimitLut[4 * 256] = {
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
	16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
	32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
	48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
	64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
	80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,
	96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
	112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
	128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
	144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
	160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
	176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
	192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
	208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
	224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
	240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
};

// kIDCTMatrix[8*x+u] = alpha(u)*cos((2*x+1)*u*M_PI/16)*sqrt(2), with fixed 13
// bit precision, where alpha(0) = 1/sqrt(2) and alpha(u) = 1 for u > 0.
// Some coefficients are off by +-1 to mimick libjpeg's behaviour.
static const int kIDCTMatrix[kDCTBlockSize] = {
	8192, 11363, 10703, 9633, 8192, 6437, 4433, 2260,
	8192, 9633, 4433, -2259, -8192, -11362, -10704, -6436,
	8192, 6437, -4433, -11362, -8192, 2261, 10704, 9633,
	8192, 2260, -10703, -6436, 8192, 9633, -4433, -11363,
	8192, -2260, -10703, 6436, 8192, -9633, -4433, 11363,
	8192, -6437, -4433, 11362, -8192, -2261, 10704, -9633,
	8192, -9633, 4433, 2259, -8192, 11362, -10704, 6436,
	8192, -11363, 10703, -9633, 8192, -6437, 4433, -2260,
};

// kIsValidMarker[i] == 1 means (0xc0 + i) is a valid marker.

static const uint8_t kIsValidMarker[] = {
	1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
};
// The DCT coefficients of a gradient in 10-bit fixed-point precision.
// The higher frequency coefficients are zeroed because they cause artifacts
// to show up.
static const int kLinearGradient[8] = { 318, -285, 81, -32, 17 * 0, -9 * 0, 5 * 0, -2 * 0 };

// Alpha(u) * sqrt(2) in 10-bit fixed-point precision.
static const int kAlphaSqrt2[8] = { 1024, 1448, 1448, 1448, 1448, 1448, 1448, 1448 };










char convt[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

void printByte(uint8_t val){//"hl"
	putchar(convt[(val & 0xF0) >> 4]);
	putchar(convt[(val & 0x0F)]);
}


int max(int a, int b){
	if (a > b){
		return a;
	}
	else{
		return b;
	}
}

int min(int a, int b){
	if (a > b){
		return b;
	}
	else{
		return a;
	}
}

uint8_t* workspace;
int workspaceIndex = 0;
int workspaceMaxUse = 0;
int workspaceTop = 28 * 1024 * 1024;//1M bottom  2M video+stack
void* workspaceMalloc(int size){
	if (workspaceIndex + size > workspaceTop){
		throw 0;
	}
	void* ret = workspace + workspaceIndex;
	workspaceIndex += size;
	if (workspaceIndex > workspaceMaxUse){
		workspaceMaxUse = workspaceIndex;
	}
	return ret;
}
void workspaceFree(int size){
	workspaceIndex -= size;
}


#define VERIFY_LEN(n)                                                   \
if (*pos + (n) > len) { \
	fprintf(stderr, "Unexpected end of input: pos=%d need=%d len=%d\n", static_cast<int>(*pos), static_cast<int>(n), static_cast<int>(len));                                     \
	jpg->error = JPEG_UNEXPECTED_EOF;                                   \
	return false;                                                       \
}

#define VERIFY_INPUT(var, low, high, code)                              \
if (var < low || var > high) { \
	fprintf(stderr, "Invalid %s: %d\n", #var, static_cast<int>(var));   \
	jpg->error = JPEG_INVALID_ ## code;                                 \
	return false;                                                   \
}

#define VERIFY_MARKER_END()                                             \
if (start_pos + marker_len != *pos) {	\
	fprintf(stderr, "Invalid marker length: declared=%d actual=%d\n", static_cast<int>(marker_len), static_cast<int>(*pos - start_pos));                        \
	jpg->error = JPEG_WRONG_MARKER_SIZE;                                \
	return false;                                                       \
}

#define EXPECT_MARKER() \
if (pos + 2 > len || data[pos] != 0xff) { \
	fprintf(stderr, "Marker byte (0xff) expected, found: %d pos=%d len=%d\n", (pos < len ? data[pos] : 0), static_cast<int>(pos), static_cast<int>(len));                                     \
	jpg->error = JPEG_MARKER_BYTE_NOT_FOUND;                            \
	return false;                                                       \
}

size_t FindNextMarker(const uint8_t* data, const size_t len, size_t pos) {
	size_t num_skipped = 0;
	while (pos + 1 < len && (data[pos] != 0xff || data[pos + 1] < 0xc0 || !kIsValidMarker[data[pos + 1] - 0xc0])) {
		++pos;
		++num_skipped;
	}
	return num_skipped;
}

// Returns ceil(a/b).
int DivCeil(int a, int b) {
	return (a + b - 1) / b;
}

int ReadUint8(const uint8_t* data, size_t* pos) {
	return data[(*pos)++];
}

int ReadUint16(const uint8_t* data, size_t* pos) {
	int v = (data[*pos] << 8) + data[*pos + 1];
	*pos += 2;
	return v;
}

// Reads the Start of Frame (SOF) marker segment and fills in *jpg with the
// parsed data.
bool ProcessSOF(const uint8_t* data, const size_t len, JpegReadMode mode, size_t* pos, JPEGData* jpg) {
	if (jpg->width != 0) {
		fprintf(stderr, "Duplicate SOF marker.\n");
		jpg->error = JPEG_DUPLICATE_SOF;
		return false;
	}
	const size_t start_pos = *pos;
	VERIFY_LEN(8);
	size_t marker_len = ReadUint16(data, pos);
	int precision = ReadUint8(data, pos);
	int height = ReadUint16(data, pos);
	int width = ReadUint16(data, pos);
	int num_components = ReadUint8(data, pos);
	VERIFY_INPUT(precision, 8, 8, PRECISION);
	VERIFY_INPUT(height, 1, 65535, HEIGHT);
	VERIFY_INPUT(width, 1, 65535, WIDTH);
	VERIFY_INPUT(num_components, 1, kMaxComponents, NUMCOMP);//kMaxComponents = 4
	VERIFY_LEN(3 * num_components);
	jpg->height = height;
	jpg->width = width;
	//jpg->components.resize(num_components);
	jpg->components = (JPEGComponent*)workspaceMalloc(num_components * sizeof(JPEGComponent));
	for (int i = 0; i < num_components; i++){
		initJPEGComponent(jpg->components+i);
	}
	jpg->componentsLen = num_components;
	// Read sampling factors and quant table index for each component.
	uint8_t ids_seen[256];
	for (int i = 0; i < 256; i++){
		ids_seen[i] = 0;
	}
	for (int i = 0; i < jpg->componentsLen; ++i) {
		const int id = ReadUint8(data, pos);
		if (ids_seen[id]) {   // (cf. section B.2.2, syntax of Ci)
			fprintf(stderr, "Duplicate ID %d in SOF.\n", id);
			jpg->error = JPEG_DUPLICATE_COMPONENT_ID;
			return false;
		}
		ids_seen[id] = 1;
		jpg->components[i].id = id;
		int factor = ReadUint8(data, pos);
		int h_samp_factor = factor >> 4;
		int v_samp_factor = factor & 0xf;
		VERIFY_INPUT(h_samp_factor, 1, 15, SAMP_FACTOR);
		VERIFY_INPUT(v_samp_factor, 1, 15, SAMP_FACTOR);
		jpg->components[i].h_samp_factor = h_samp_factor;
		jpg->components[i].v_samp_factor = v_samp_factor;
		jpg->components[i].quant_idx = ReadUint8(data, pos);
		jpg->max_h_samp_factor = max(jpg->max_h_samp_factor, h_samp_factor);
		jpg->max_v_samp_factor = max(jpg->max_v_samp_factor, v_samp_factor);
	}

	// We have checked above that none of the sampling factors are 0, so the max
	// sampling factors can not be 0.
	jpg->MCU_rows = DivCeil(jpg->height, jpg->max_v_samp_factor * 8);
	jpg->MCU_cols = DivCeil(jpg->width, jpg->max_h_samp_factor * 8);
	// Compute the block dimensions for each component.
	if (mode == JPEG_READ_ALL) {
		for (int i = 0; i < jpg->componentsLen; ++i) {
			JPEGComponent* c = &jpg->components[i];
			if (jpg->max_h_samp_factor % c->h_samp_factor != 0 || jpg->max_v_samp_factor % c->v_samp_factor != 0) {
				fprintf(stderr, "Non-integral subsampling ratios.\n");
				jpg->error = JPEG_INVALID_SAMPLING_FACTORS;
				return false;
			}
			c->width_in_blocks = jpg->MCU_cols * c->h_samp_factor;
			c->height_in_blocks = jpg->MCU_rows * c->v_samp_factor;
			const uint64_t num_blocks = static_cast<uint64_t>(c->width_in_blocks) * c->height_in_blocks;
			if (num_blocks > (1ULL << 21)) {
				// Refuse to allocate more than 1 GB of memory for the coefficients,
				// that is 2M blocks x 64 coeffs x 2 bytes per coeff x max 4 components.
				// TODO Add this limit to a GuetzliParams struct.
				fprintf(stderr, "Image too large.\n");
				jpg->error = JPEG_IMAGE_TOO_LARGE;
				return false;
			}
			c->num_blocks = static_cast<int>(num_blocks);
			//c->coeffs.resize(c->num_blocks * kDCTBlockSize);
			c->coeffsLen = c->num_blocks * kDCTBlockSize;
			c->coeffs = (coeff_t*)workspaceMalloc(c->coeffsLen * sizeof(coeff_t));
			for (int i = 0; i < c->coeffsLen; i++){
				c->coeffs[i] = 0;
			}
		}
	}
	VERIFY_MARKER_END();
	return true;
}

// Returns the table width of the next 2nd level table, count is the histogram
// of bit lengths for the remaining symbols, len is the code length of the next
// processed symbol.
int NextTableBitSize(const int* count, int len) {
	int left = 1 << (len - kJpegHuffmanRootTableBits);
	while (len < kJpegHuffmanMaxBitLength) {
		left -= count[len];
		if (left <= 0) break;
		++len;
		left <<= 1;
	}
	return len - kJpegHuffmanRootTableBits;
}

int BuildJpegHuffmanTable(const int* count_in, const int* symbols, HuffmanTableEntry* lut) {
	HuffmanTableEntry code;    // current table entry
	HuffmanTableEntry* table;  // next available space in table
	int len;         // current code length
	int idx;         // symbol index
	int key;         // prefix code
	int reps;        // number of replicate key values in current table
	int low;         // low bits for current root entry
	int table_bits;  // key length of current table
	int table_size;  // size of current table
	int total_size;  // sum of root table size and 2nd level table sizes

	// Make a local copy of the input bit length histogram.
	int count[kJpegHuffmanMaxBitLength + 1];
	for (int i = 0; i<kJpegHuffmanMaxBitLength + 1; i++){
		count[i] = 0;
	}
	int total_count = 0;
	for (len = 1; len <= kJpegHuffmanMaxBitLength; ++len) {
		count[len] = count_in[len];
		total_count += count[len];
	}

	table = lut;
	table_bits = kJpegHuffmanRootTableBits;
	table_size = 1 << table_bits;
	total_size = table_size;

	// Special case code with only one value.
	if (total_count == 1) {
		code.bits = 0;
		code.value = symbols[0];
		for (key = 0; key < total_size; ++key) {
			table[key] = code;
		}
		return total_size;
	}

	// Fill in root table.
	key = 0;
	idx = 0;
	for (len = 1; len <= kJpegHuffmanRootTableBits; ++len) {
		for (; count[len] > 0; --count[len]) {
			code.bits = len;
			code.value = symbols[idx++];
			reps = 1 << (kJpegHuffmanRootTableBits - len);
			while (reps--) {
				table[key++] = code;
			}
		}
	}

	// Fill in 2nd level tables and add pointers to root table.
	table += table_size;
	table_size = 0;
	low = 0;
	for (len = kJpegHuffmanRootTableBits + 1;
		len <= kJpegHuffmanMaxBitLength; ++len) {
		for (; count[len] > 0; --count[len]) {
			// Start a new sub-table if the previous one is full.
			if (low >= table_size) {
				table += table_size;
				table_bits = NextTableBitSize(count, len);
				table_size = 1 << table_bits;
				total_size += table_size;
				low = 0;
				lut[key].bits = table_bits + kJpegHuffmanRootTableBits;
				lut[key].value = (table - lut) - key;
				++key;
			}
			code.bits = len - kJpegHuffmanRootTableBits;
			code.value = symbols[idx++];
			reps = 1 << (table_bits - code.bits);
			while (reps--) {
				table[low++] = code;
			}
		}
	}

	return total_size;
}

//##########################################################################################################################################################################################

// Reads the Start of Scan (SOS) marker segment and fills in *scan_info with the
// parsed data.
bool ProcessSOS(const uint8_t* data, const size_t len, size_t* pos, JPEGData* jpg) {
	const size_t start_pos = *pos;
	VERIFY_LEN(3);
	size_t marker_len = ReadUint16(data, pos);
	int comps_in_scan = ReadUint8(data, pos);
	VERIFY_INPUT(comps_in_scan, 1, jpg->componentsLen, COMPS_IN_SCAN);

	JPEGScanInfo* scan_info = &(jpg->scan_info);
	scan_info->componentsLen = comps_in_scan;
	//scan_info.components.resize(comps_in_scan);
	scan_info->components = (JPEGComponentScanInfo*)workspaceMalloc(comps_in_scan * sizeof(JPEGComponentScanInfo));
	VERIFY_LEN(2 * comps_in_scan);
	uint8_t ids_seen[256];
	for (int i = 0; i < 256; i++){
		ids_seen[i] = 0;
	}
	for (int i = 0; i < comps_in_scan; ++i) {
		int id = ReadUint8(data, pos);
		if (ids_seen[id]) {   // (cf. section B.2.3, regarding CSj)
			fprintf(stderr, "Duplicate ID %d in SOS.\n", id);
			jpg->error = JPEG_DUPLICATE_COMPONENT_ID;
			return false;
		}
		ids_seen[id] = 1;
		bool found_index = false;
		for (int j = 0; j < jpg->componentsLen; ++j) {
			if (jpg->components[j].id == id) {
				scan_info->components[i].comp_idx = j;
				found_index = true;
			}
		}
		if (!found_index) {
			fprintf(stderr, "SOS marker: Could not find component with id %d\n", id);
			jpg->error = JPEG_COMPONENT_NOT_FOUND;
			return false;
		}
		int c = ReadUint8(data, pos);
		int dc_tbl_idx = c >> 4;
		int ac_tbl_idx = c & 0xf;
		VERIFY_INPUT(dc_tbl_idx, 0, 3, HUFFMAN_INDEX);
		VERIFY_INPUT(ac_tbl_idx, 0, 3, HUFFMAN_INDEX);
		scan_info->components[i].dc_tbl_idx = dc_tbl_idx;
		scan_info->components[i].ac_tbl_idx = ac_tbl_idx;
	}
	VERIFY_LEN(3);
	scan_info->Ss = ReadUint8(data, pos);
	scan_info->Se = ReadUint8(data, pos);
	VERIFY_INPUT(scan_info->Ss, 0, 63, START_OF_SCAN);
	VERIFY_INPUT(scan_info->Se, scan_info->Ss, 63, END_OF_SCAN);
	int c = ReadUint8(data, pos);
	scan_info->Ah = c >> 4;
	scan_info->Al = c & 0xf;
	// Check that all the Huffman tables needed for this scan are defined.
	for (int i = 0; i < comps_in_scan; ++i) {
		bool found_dc_table = false;
		bool found_ac_table = false;
		myVector* huffman_code = jpg->huffman_code;
		for (int j = 0; j < jpg->huffman_codeLen; ++j) {
			int slot_id = *((int*)huffman_code->p);// jpg->huffman_code[j].slot_id;
			huffman_code = huffman_code->next;
			if (slot_id == scan_info->components[i].dc_tbl_idx) {
				found_dc_table = true;
			}
			else if (slot_id == scan_info->components[i].ac_tbl_idx + 16) {
				found_ac_table = true;
			}
		}
		if (scan_info->Ss == 0 && !found_dc_table) {
			fprintf(stderr, "SOS marker: Could not find DC Huffman table with index %d\n", scan_info->components[i].dc_tbl_idx);
			jpg->error = JPEG_HUFFMAN_TABLE_NOT_FOUND;
			return false;
		}
		if (scan_info->Se > 0 && !found_ac_table) {
			fprintf(stderr, "SOS marker: Could not find AC Huffman table with index %d\n", scan_info->components[i].ac_tbl_idx);
			jpg->error = JPEG_HUFFMAN_TABLE_NOT_FOUND;
			return false;
		}
	}
	VERIFY_MARKER_END();
	return true;
}

// Reads the Define Huffman Table (DHT) marker segment and fills in *jpg with
// the parsed data. Builds the Huffman decoding table in either dc_huff_lut or
// ac_huff_lut, depending on the type and solt_id of Huffman code being read.
bool ProcessDHT(const uint8_t* data, const size_t len, JpegReadMode mode, HuffmanTableEntry* dc_huff_lut, HuffmanTableEntry* ac_huff_lut, size_t* pos, JPEGData* jpg) {
	const size_t start_pos = *pos;
	VERIFY_LEN(2);
	size_t marker_len = ReadUint16(data, pos);
	if (marker_len == 2) {
		fprintf(stderr, "DHT marker: no Huffman table found\n");
		jpg->error = JPEG_EMPTY_DHT;
		return false;
	}
	while (*pos < start_pos + marker_len) {
		VERIFY_LEN(1 + kJpegHuffmanMaxBitLength);
		int huffman_index = ReadUint8(data, pos);
		//JPEGHuffmanCode huff;
		{//for check
			myVector* huff = (myVector*)workspaceMalloc(sizeof(myVector));
			huff->next = 0;
			if (jpg->huffman_code){
				myVector* next = jpg->huffman_code;
				while (next->next){
					next = next->next;
				}
				next->next = huff;
			}
			else{
				jpg->huffman_code = huff;
			}
			jpg->huffman_codeLen++;
			int* slot_id = (int*)workspaceMalloc(sizeof(int));

			*slot_id = huffman_index;
			huff->p = slot_id;
		}

		int is_ac_table = (huffman_index & 0x10) != 0;
		HuffmanTableEntry* huff_lut;
		if (is_ac_table) {
			huffman_index -= 0x10;
			VERIFY_INPUT(huffman_index, 0, 3, HUFFMAN_INDEX);
			huff_lut = ac_huff_lut + (huffman_index * kJpegHuffmanLutSize);
		}
		else {
			VERIFY_INPUT(huffman_index, 0, 3, HUFFMAN_INDEX);
			huff_lut = dc_huff_lut + (huffman_index * kJpegHuffmanLutSize);
		}
		int* counts = (int*)workspaceMalloc((kJpegHuffmanMaxBitLength + 1) * sizeof(int));
		counts[0] = 0;
		int total_count = 0;
		int space = 1 << kJpegHuffmanMaxBitLength;
		int max_depth = 1;
		for (int i = 1; i <= kJpegHuffmanMaxBitLength; ++i) {
			int count = ReadUint8(data, pos);
			if (count != 0) {
				max_depth = i;
			}
			counts[i] = count;
			total_count += count;
			space -= count * (1 << (kJpegHuffmanMaxBitLength - i));
		}
		if (is_ac_table) {
			VERIFY_INPUT(total_count, 0, kJpegHuffmanAlphabetSize, HUFFMAN_CODE);
		}
		else {
			VERIFY_INPUT(total_count, 0, kJpegDCAlphabetSize, HUFFMAN_CODE);
		}
		VERIFY_LEN(total_count);
		uint8_t* values_seen = (uint8_t*)workspaceMalloc(256 * sizeof(uint8_t));
		for (int i = 0; i < 256; i++){
			values_seen[i] = 0;
		}
		int* values = (int*)workspaceMalloc((kJpegHuffmanAlphabetSize + 1) * sizeof(int));

		for (int i = 0; i < total_count; ++i) {
			uint8_t value = ReadUint8(data, pos);
			int v2 = value;
			if (!is_ac_table) {
				VERIFY_INPUT(v2, 0, kJpegDCAlphabetSize - 1, HUFFMAN_CODE);
			}
			if (values_seen[value]) {
				fprintf(stderr, "Duplicate Huffman code value %d\n", value);
				jpg->error = JPEG_INVALID_HUFFMAN_CODE;
				return false;
			}
			values_seen[value] = 1;
			values[i] = value;
		}
		// Add an invalid symbol that will have the all 1 code.
		counts[max_depth]++;
		values[total_count] = kJpegHuffmanAlphabetSize;
		space -= (1 << (kJpegHuffmanMaxBitLength - max_depth));
		if (space < 0) {
			fprintf(stderr, "Invalid Huffman code lengths.\n");
			jpg->error = JPEG_INVALID_HUFFMAN_CODE;
			return false;
		}
		else if (space > 0 && huff_lut[0].value != 0xffff) {
			// Re-initialize the values to an invalid symbol so that we can recognize
			// it when reading the bit stream using a Huffman code with space > 0.
			for (int i = 0; i < kJpegHuffmanLutSize; ++i) {
				huff_lut[i].bits = 0;
				huff_lut[i].value = 0xffff;
			}
		}
		//huff.is_last = (*pos == start_pos + marker_len);
		if (mode == JPEG_READ_ALL && !BuildJpegHuffmanTable(counts, values, huff_lut)) {
			fprintf(stderr, "Failed to build Huffman table.\n");
			jpg->error = JPEG_INVALID_HUFFMAN_CODE;
			return false;
		}
		workspaceFree((kJpegHuffmanAlphabetSize + 1) * sizeof(int));
		workspaceFree(256 * sizeof(uint8_t));
		workspaceFree((kJpegHuffmanMaxBitLength + 1) * sizeof(int));
		//jpg->huffman_code.push_back(huff);
	}
	VERIFY_MARKER_END();
	return true;
}

// Helper structure to read bits from the entropy coded data segment.
struct BitReaderState {
	void initBitReaderState(uint8_t* data, size_t len, size_t pos){
		data_ = (data);
		len_ = (len);
		Reset(pos);
	}

	void Reset(size_t pos) {
		pos_ = pos;
		val_ = 0;
		bits_left_ = 0;
		next_marker_pos_ = len_ - 2;
		FillBitWindow();
	}

	// Returns the next byte and skips the 0xff/0x00 escape sequences.
	uint8_t GetNextByte() {
		if (pos_ >= next_marker_pos_) {
			++pos_;
			return 0;
		}
		uint8_t c = data_[pos_++];
		if (c == 0xff) {
			uint8_t escape = data_[pos_];
			if (escape == 0) {
				++pos_;
			}
			else {
				// 0xff was followed by a non-zero byte, which means that we found the
				// start of the next marker segment.
				next_marker_pos_ = pos_ - 1;
			}
		}
		return c;
	}

	void FillBitWindow() {
		if (bits_left_ <= 16) {
			while (bits_left_ <= 56) {
				val_ <<= 8;
				val_ |= (uint64_t)GetNextByte();
				bits_left_ += 8;
			}
		}
	}

	int ReadBits(int nbits) {
		FillBitWindow();
		uint64_t val = (val_ >> (bits_left_ - nbits)) & ((1ULL << nbits) - 1);
		bits_left_ -= nbits;
		return val;
	}

	// Sets *pos to the next stream position where parsing should continue.
	// Returns false if the stream ended too early.
	bool FinishStream(size_t* pos) {
		// Give back some bytes that we did not use.
		int unused_bytes_left = bits_left_ >> 3;
		while (unused_bytes_left-- > 0) {
			pos_--;
			// If we give back a 0 byte, we need to check if it was a 0xff/0x00 escape
			// sequence, and if yes, we need to give back one more byte.
			if (pos_ < next_marker_pos_ &&
				data_[pos_] == 0 && data_[pos_ - 1] == 0xff) {
				pos_--;
			}
		}
		if (pos_ > next_marker_pos_) {
			// Data ran out before the scan was complete.
			fprintf(stderr, "Unexpected end of scan.\n");
			return false;
		}
		*pos = pos_;
		return true;
	}

	uint8_t* data_;
	size_t len_;
	size_t pos_;
	uint64_t val_;
	int bits_left_;
	size_t next_marker_pos_;
};

// Returns the next Huffman-coded symbol.
int ReadSymbol(const HuffmanTableEntry* table, BitReaderState* br) {
	int nbits;
	br->FillBitWindow();
	int val = (br->val_ >> (br->bits_left_ - 8)) & 0xff;
	table += val;
	nbits = table->bits - 8;
	if (nbits > 0) {
		br->bits_left_ -= 8;
		table += table->value;
		val = (br->val_ >> (br->bits_left_ - nbits)) & ((1 << nbits) - 1);
		table += val;
	}
	br->bits_left_ -= table->bits;
	return table->value;
}

// Returns the DC diff or AC value for extra bits value x and prefix code s.
// See Tables F.1 and F.2 of the spec.
int HuffExtend(int x, int s) {
	return (x < (1 << (s - 1)) ? x + ((-1) << s) + 1 : x);
}

// Decodes one 8x8 block of DCT coefficients from the bit stream.
bool DecodeDCTBlock(const HuffmanTableEntry* dc_huff, const HuffmanTableEntry* ac_huff, int Ss, int Se, int Al, int* eobrun, BitReaderState* br, JPEGData* jpg, coeff_t* last_dc_coeff, coeff_t* coeffs) {
	int s;
	int r;
	bool eobrun_allowed = Ss > 0;
	if (Ss == 0) {
		s = ReadSymbol(dc_huff, br);
		if (s >= kJpegDCAlphabetSize) {
			fprintf(stderr, "Invalid Huffman symbol %d for DC coefficient.\n", s);
			jpg->error = JPEG_INVALID_SYMBOL;
			return false;
		}
		if (s > 0) {
			r = br->ReadBits(s);
			s = HuffExtend(r, s);
		}
		s += *last_dc_coeff;
		const int dc_coeff = s << Al;
		coeffs[0] = dc_coeff;
		if (dc_coeff != coeffs[0]) {
			fprintf(stderr, "Invalid DC coefficient %d\n", dc_coeff);
			jpg->error = JPEG_NON_REPRESENTABLE_DC_COEFF;
			return false;
		}
		*last_dc_coeff = s;
		++Ss;
	}
	if (Ss > Se) {
		return true;
	}
	if (*eobrun > 0) {
		--(*eobrun);
		return true;
	}
	for (int k = Ss; k <= Se; k++) {
		s = ReadSymbol(ac_huff, br);
		if (s >= kJpegHuffmanAlphabetSize) {
			fprintf(stderr, "Invalid Huffman symbol %d for AC coefficient %d\n",
				s, k);
			jpg->error = JPEG_INVALID_SYMBOL;
			return false;
		}
		r = s >> 4;
		s &= 15;
		if (s > 0) {
			k += r;
			if (k > Se) {
				fprintf(stderr, "Out-of-band coefficient %d band was %d-%d\n",
					k, Ss, Se);
				jpg->error = JPEG_OUT_OF_BAND_COEFF;
				return false;
			}
			if (s + Al >= kJpegDCAlphabetSize) {
				fprintf(stderr, "Out of range AC coefficient value: s=%d Al=%d k=%d\n",
					s, Al, k);
				jpg->error = JPEG_NON_REPRESENTABLE_AC_COEFF;
				return false;
			}
			r = br->ReadBits(s);
			s = HuffExtend(r, s);
			coeffs[kJPEGNaturalOrder[k]] = s << Al;
		}
		else if (r == 15) {
			k += 15;
		}
		else {
			*eobrun = 1 << r;
			if (r > 0) {
				if (!eobrun_allowed) {
					fprintf(stderr, "End-of-block run crossing DC coeff.\n");
					jpg->error = JPEG_EOB_RUN_TOO_LONG;
					return false;
				}
				*eobrun += br->ReadBits(r);
			}
			break;
		}
	}
	--(*eobrun);
	return true;
}

bool RefineDCTBlock(const HuffmanTableEntry* ac_huff, int Ss, int Se, int Al, int* eobrun, BitReaderState* br, JPEGData* jpg, coeff_t* coeffs) {
	bool eobrun_allowed = Ss > 0;
	if (Ss == 0) {
		int s = br->ReadBits(1);
		coeff_t dc_coeff = coeffs[0];
		dc_coeff |= s << Al;
		coeffs[0] = dc_coeff;
		++Ss;
	}
	if (Ss > Se) {
		return true;
	}
	int p1 = 1 << Al;
	int m1 = (-1) << Al;
	int k = Ss;
	int r;
	int s;
	bool in_zero_run = false;
	if (*eobrun <= 0) {
		for (; k <= Se; k++) {
			s = ReadSymbol(ac_huff, br);
			if (s >= kJpegHuffmanAlphabetSize) {
				fprintf(stderr, "Invalid Huffman symbol %d for AC coefficient %d\n",
					s, k);
				jpg->error = JPEG_INVALID_SYMBOL;
				return false;
			}
			r = s >> 4;
			s &= 15;
			if (s) {
				if (s != 1) {
					fprintf(stderr, "Invalid Huffman symbol %d for AC coefficient %d\n",
						s, k);
					jpg->error = JPEG_INVALID_SYMBOL;
					return false;
				}
				s = br->ReadBits(1) ? p1 : m1;
				in_zero_run = false;
			}
			else {
				if (r != 15) {
					*eobrun = 1 << r;
					if (r > 0) {
						if (!eobrun_allowed) {
							fprintf(stderr, "End-of-block run crossing DC coeff.\n");
							jpg->error = JPEG_EOB_RUN_TOO_LONG;
							return false;
						}
						*eobrun += br->ReadBits(r);
					}
					break;
				}
				in_zero_run = true;
			}
			do {
				coeff_t thiscoef = coeffs[kJPEGNaturalOrder[k]];
				if (thiscoef != 0) {
					if (br->ReadBits(1)) {
						if ((thiscoef & p1) == 0) {
							if (thiscoef >= 0) {
								thiscoef += p1;
							}
							else {
								thiscoef += m1;
							}
						}
					}
					coeffs[kJPEGNaturalOrder[k]] = thiscoef;
				}
				else {
					if (--r < 0) {
						break;
					}
				}
				k++;
			} while (k <= Se);
			if (s) {
				if (k > Se) {
					fprintf(stderr, "Out-of-band coefficient %d band was %d-%d\n",
						k, Ss, Se);
					jpg->error = JPEG_OUT_OF_BAND_COEFF;
					return false;
				}
				coeffs[kJPEGNaturalOrder[k]] = s;
			}
		}
	}
	if (in_zero_run) {
		fprintf(stderr, "Extra zero run before end-of-block.\n");
		jpg->error = JPEG_EXTRA_ZERO_RUN;
		return false;
	}
	if (*eobrun > 0) {
		for (; k <= Se; k++) {
			coeff_t thiscoef = coeffs[kJPEGNaturalOrder[k]];
			if (thiscoef != 0) {
				if (br->ReadBits(1)) {
					if ((thiscoef & p1) == 0) {
						if (thiscoef >= 0) {
							thiscoef += p1;
						}
						else {
							thiscoef += m1;
						}
					}
				}
				coeffs[kJPEGNaturalOrder[k]] = thiscoef;
			}
		}
	}
	--(*eobrun);
	return true;
}

bool ProcessRestart(const uint8_t* data, const size_t len, int* next_restart_marker, BitReaderState* br, JPEGData* jpg) {
	size_t pos = 0;
	if (!br->FinishStream(&pos)) {
		jpg->error = JPEG_INVALID_SCAN;
		return false;
	}
	int expected_marker = 0xd0 + *next_restart_marker;
	EXPECT_MARKER();
	int marker = data[pos + 1];
	if (marker != expected_marker) {
		fprintf(stderr, "Did not find expected restart marker %d actual=%d\n",
			expected_marker, marker);
		jpg->error = JPEG_WRONG_RESTART_MARKER;
		return false;
	}
	br->Reset(pos + 2);
	*next_restart_marker += 1;
	*next_restart_marker &= 0x7;
	return true;
}

//kMaxComponents = 4
bool ProcessScan(uint8_t* data, size_t len, const HuffmanTableEntry* dc_huff_lut, const HuffmanTableEntry* ac_huff_lut, uint16_t scan_progression[kMaxComponents][kDCTBlockSize], bool is_progressive, size_t* pos, JPEGData* jpg) {
	if (!ProcessSOS(data, len, pos, jpg)) {
		return false;
	}
	JPEGScanInfo* scan_info = &(jpg->scan_info);
	bool is_interleaved = (scan_info->componentsLen > 1);
	int MCUs_per_row;
	int MCU_rows;
	if (is_interleaved) {
		MCUs_per_row = jpg->MCU_cols;
		MCU_rows = jpg->MCU_rows;
	}
	else {
		const JPEGComponent& c = jpg->components[scan_info->components[0].comp_idx];
		MCUs_per_row = DivCeil(jpg->width * c.h_samp_factor, 8 * jpg->max_h_samp_factor);
		MCU_rows = DivCeil(jpg->height * c.v_samp_factor, 8 * jpg->max_v_samp_factor);
	}
	coeff_t last_dc_coeff[kMaxComponents];
	for (int i = 0; i < kMaxComponents; i++){
		last_dc_coeff[i] = 0;//kMaxComponents = 4
	}
	BitReaderState br;
	br.initBitReaderState(data, len, *pos);
	int restarts_to_go = jpg->restart_interval;
	int next_restart_marker = 0;
	int eobrun = -1;
	int block_scan_index = 0;
	const int Al = is_progressive ? scan_info->Al : 0;
	const int Ah = is_progressive ? scan_info->Ah : 0;
	const int Ss = is_progressive ? scan_info->Ss : 0;
	const int Se = is_progressive ? scan_info->Se : 63;
	const uint16_t scan_bitmask = Ah == 0 ? (0xffff << Al) : (1u << Al);
	const uint16_t refinement_bitmask = (1 << Al) - 1;
	for (int i = 0; i < scan_info->componentsLen; ++i) {
		int comp_idx = scan_info->components[i].comp_idx;
		for (int k = Ss; k <= Se; ++k) {
			if (scan_progression[comp_idx][k] & scan_bitmask) {
				fprintf(stderr, "Overlapping scans: component=%d k=%d prev_mask=%d cur_mask=%d\n", comp_idx, k, scan_progression[i][k], scan_bitmask);
				jpg->error = JPEG_OVERLAPPING_SCANS;
				return false;
			}
			if (scan_progression[comp_idx][k] & refinement_bitmask) {
				fprintf(stderr, "Invalid scan order, a more refined scan was already done: component=%d k=%d prev_mask=%d cur_mask=%d\n", comp_idx, k, scan_progression[i][k], scan_bitmask);
				jpg->error = JPEG_INVALID_SCAN_ORDER;
				return false;
			}
			scan_progression[comp_idx][k] |= scan_bitmask;
		}
	}
	if (Al > 10) {
		fprintf(stderr, "Scan parameter Al=%d is not supported in knusperli.\n", Al);
		jpg->error = JPEG_NON_REPRESENTABLE_AC_COEFF;
		return false;
	}
	for (int mcu_y = 0; mcu_y < MCU_rows; ++mcu_y) {
		for (int mcu_x = 0; mcu_x < MCUs_per_row; ++mcu_x) {
			// Handle the restart intervals.
			if (jpg->restart_interval > 0) {
				if (restarts_to_go == 0) {
					if (ProcessRestart(data, len,
						&next_restart_marker, &br, jpg)) {
						restarts_to_go = jpg->restart_interval;
						//memset(last_dc_coeff, 0, sizeof(last_dc_coeff));
						for (int i = 0; i<kMaxComponents; i++){
							last_dc_coeff[i] = 0;
						}
						if (eobrun > 0) {
							fprintf(stderr, "End-of-block run too long.\n");
							jpg->error = JPEG_EOB_RUN_TOO_LONG;
							return false;
						}
						eobrun = -1;   // fresh start
					}
					else {
						return false;
					}
				}
				--restarts_to_go;
			}
			// Decode one MCU.
			for (int i = 0; i < scan_info->componentsLen; ++i) {
				JPEGComponentScanInfo* si = &scan_info->components[i];
				JPEGComponent* c = &jpg->components[si->comp_idx];
				const HuffmanTableEntry* dc_lut = &dc_huff_lut[si->dc_tbl_idx * kJpegHuffmanLutSize];
				const HuffmanTableEntry* ac_lut = &ac_huff_lut[si->ac_tbl_idx * kJpegHuffmanLutSize];
				int nblocks_y = is_interleaved ? c->v_samp_factor : 1;
				int nblocks_x = is_interleaved ? c->h_samp_factor : 1;
				for (int iy = 0; iy < nblocks_y; ++iy) {
					for (int ix = 0; ix < nblocks_x; ++ix) {
						int block_y = mcu_y * nblocks_y + iy;
						int block_x = mcu_x * nblocks_x + ix;
						int block_idx = block_y * c->width_in_blocks + block_x;
						coeff_t* coeffs = &c->coeffs[block_idx * kDCTBlockSize];
						if (Ah == 0) {
							if (!DecodeDCTBlock(dc_lut, ac_lut, Ss, Se, Al, &eobrun, &br, jpg, &last_dc_coeff[si->comp_idx], coeffs)) {
								return false;
							}
						}
						else {
							if (!RefineDCTBlock(ac_lut, Ss, Se, Al, &eobrun, &br, jpg, coeffs)) {
								return false;
							}
						}
						++block_scan_index;
					}
				}
			}
		}
	}
	if (eobrun > 0) {
		fprintf(stderr, "End-of-block run too long.\n");
		jpg->error = JPEG_EOB_RUN_TOO_LONG;
		return false;
	}
	if (!br.FinishStream(pos)) {
		jpg->error = JPEG_INVALID_SCAN;
		return false;
	}
	if (*pos > len) {
		fprintf(stderr, "Unexpected end of file during scan. pos=%d len=%d\n", static_cast<int>(*pos), static_cast<int>(len));
		jpg->error = JPEG_UNEXPECTED_EOF;
		return false;
	}
	return true;
}
 
// Reads the Define Quantization Table (DQT) marker segment and fills in *jpg
// with the parsed data.
bool ProcessDQT(const uint8_t* data, const size_t len, size_t* pos, JPEGData* jpg) {
	const size_t start_pos = *pos;
	VERIFY_LEN(2);
	size_t marker_len = ReadUint16(data, pos);
	if (marker_len == 2) {
		fprintf(stderr, "DQT marker: no quantization table found\n");
		jpg->error = JPEG_EMPTY_DQT;
		return false;
	}
	while (*pos < start_pos + marker_len && jpg->quantLen < kMaxQuantTables) {
		VERIFY_LEN(1);
		int quant_table_index = ReadUint8(data, pos);
		int quant_table_precision = quant_table_index >> 4;
		quant_table_index &= 0xf;
		VERIFY_INPUT(quant_table_index, 0, 3, QUANT_TBL_INDEX);
		VERIFY_LEN((quant_table_precision ? 2 : 1) * kDCTBlockSize);

		JPEGQuantTable* table = (JPEGQuantTable*)workspaceMalloc(sizeof(JPEGQuantTable));
		initJPEGQuantTable(table);
		table->values = (int*)workspaceMalloc(kDCTBlockSize * sizeof(int));
		table->index = quant_table_index;
		//table->precision = quant_table_precision;
		for (int i = 0; i < kDCTBlockSize; ++i) {
			int quant_val = quant_table_precision ?
				ReadUint16(data, pos) :
				ReadUint8(data, pos);
			VERIFY_INPUT(quant_val, 1, 65535, QUANT_VAL);
			table->values[kJPEGNaturalOrder[i]] = quant_val;
		}
		//table->is_last = (*pos == start_pos + marker_len);
		jpg->quantLen++;
		//jpg->quant.push_back(table);
		myVector* v = (myVector*)workspaceMalloc(sizeof(myVector));
		v->p = table;
		v->next = 0;
		if (jpg->quant){
			myVector* next = jpg->quant;
			while (next->next){
				next = next->next;
			}
			next->next = v;
		}
		else{
			jpg->quant = v;
		}


	}
	VERIFY_MARKER_END();
	return true;
}

// Reads the DRI marker and saved the restart interval into *jpg.
bool ProcessDRI(const uint8_t* data, const size_t len, size_t* pos, JPEGData* jpg) {
	if (jpg->restart_interval > 0) {
		fprintf(stderr, "Duplicate DRI marker.\n");
		jpg->error = JPEG_DUPLICATE_DRI;
		return false;
	}
	const size_t start_pos = *pos;
	VERIFY_LEN(4);
	size_t marker_len = ReadUint16(data, pos);
	int restart_interval = ReadUint16(data, pos);
	jpg->restart_interval = restart_interval;
	VERIFY_MARKER_END();
	return true;
}

// Saves the APP marker segment as a string to *jpg.
bool ProcessAPP(const uint8_t* data, const size_t len, size_t* pos, JPEGData* jpg) {
	VERIFY_LEN(2);
	size_t marker_len = ReadUint16(data, pos);
	VERIFY_INPUT(marker_len, 2, 65535, MARKER_LEN);
	VERIFY_LEN(marker_len - 2);
	// Save the marker type together with the app data.

	//std::string app_str(reinterpret_cast<const char*>(&data[*pos - 3]), marker_len + 1);
	myVector* v = (myVector*)workspaceMalloc(sizeof(myVector));
	mystr* s = (mystr*)workspaceMalloc(sizeof(mystr));
	s->len = marker_len + 1;
	s->str = &data[*pos - 3];
	v->p = s;
	v->next = 0;
	*pos += marker_len - 2;
	//jpg->app_data.push_back(app_str);

	if (jpg->app_data){
		myVector* next = jpg->app_data;
		while (next->next){
			next = next->next;
		}
		next->next = v;
	}
	else{
		jpg->app_data = v;
	}
	return true;
}

// Saves the COM marker segment as a string to *jpg.
bool ProcessCOM(const uint8_t* data, const size_t len, size_t* pos, JPEGData* jpg) {
	VERIFY_LEN(2);
	size_t marker_len = ReadUint16(data, pos);
	VERIFY_INPUT(marker_len, 2, 65535, MARKER_LEN);
	VERIFY_LEN(marker_len - 2);
	//std::string com_str(reinterpret_cast<const char*>(&data[*pos - 2]), marker_len);
	*pos += marker_len - 2;
////jpg->com_data.push_back(com_str);
	return true;
}

// Changes the quant_idx field of the components to refer to the index of the
// quant table in the jpg->quant array.
bool FixupIndexes(JPEGData* jpg) {
	for (int i = 0; i < jpg->componentsLen; ++i) {
		JPEGComponent* c = &jpg->components[i];
		bool found_index = false;
		
		myVector* v = jpg->quant;
		for (int j = 0; j < jpg->quantLen; ++j) {
			JPEGQuantTable* table = (JPEGQuantTable*)v->p;
			v = v->next;
			//if (jpg->quant[j].index == c->quant_idx) {
			if (table->index == c->quant_idx) {
				c->quant_idx = j;
				found_index = true;
				break;
			}
		}
		if (!found_index) {
			fprintf(stderr, "Quantization table with index %d not found\n",
				c->quant_idx);
			jpg->error = JPEG_QUANT_TABLE_NOT_FOUND;
			return false;
		}
	}
	return true;
}

bool ReadJpeg(uint8_t* data, size_t len, JpegReadMode mode, JPEGData* jpg) {
	size_t pos = 0;
	// Check SOI marker.
	EXPECT_MARKER();
	int marker = data[pos + 1];
	pos += 2;
	if (marker != 0xd8) {
		fprintf(stderr, "Did not find expected SOI marker, actual=%d\n", marker);
		jpg->error = JPEG_SOI_NOT_FOUND;
		return false;
	}
	int lut_size = kMaxHuffmanTables * kJpegHuffmanLutSize;
	HuffmanTableEntry* dc_huff_lut = (HuffmanTableEntry*)workspaceMalloc(lut_size * sizeof(HuffmanTableEntry));
	HuffmanTableEntry* ac_huff_lut = (HuffmanTableEntry*)workspaceMalloc(lut_size * sizeof(HuffmanTableEntry));
	for (int i = 0; i < lut_size; i++){
		initHuffmanTableEntry(dc_huff_lut + i);
		initHuffmanTableEntry(ac_huff_lut + i);
	}
	bool found_sof = false;
	bool found_dht = false;
	uint16_t scan_progression[kMaxComponents][kDCTBlockSize];//kMaxComponents = 4 kDCTBlockSize = 64
	for (int i = 0; i < kMaxComponents; i++){
		for (int j = 0; j < kDCTBlockSize; j++){
			scan_progression[i][j] = 0;
		}
	}
	bool is_progressive = false;   // default
	do {
		// Read next marker.
		size_t num_skipped = FindNextMarker(data, len, pos);
		if (num_skipped > 0) {
			// Add a fake marker to indicate arbitrary in-between-markers data.
			////jpg->marker_order.push_back(0xff);
			////jpg->inter_marker_data.push_back(std::string(reinterpret_cast<const char*>(&data[pos]),num_skipped)); not used 
			pos += num_skipped;
		}
		EXPECT_MARKER();
		marker = data[pos + 1];
		pos += 2;
		bool ok = true;
		switch (marker) {
		case 0xc0:
		case 0xc1:
		case 0xc2:
			is_progressive = (marker == 0xc2);
			ok = ProcessSOF(data, len, mode, &pos, jpg);
			found_sof = true;
			break;
		case 0xc4:
			ok = ProcessDHT(data, len, mode, dc_huff_lut, ac_huff_lut, &pos, jpg);
			found_dht = true;
			break;
		case 0xd0:
		case 0xd1:
		case 0xd2:
		case 0xd3:
		case 0xd4:
		case 0xd5:
		case 0xd6:
		case 0xd7:
			// RST markers do not have any data.
			break;
		case 0xd9:
			// Found end marker.
			break;
		case 0xda:
			if (mode == JPEG_READ_ALL) {
				ok = ProcessScan(data, len, dc_huff_lut, ac_huff_lut, scan_progression, is_progressive, &pos, jpg);
			}
			break;
		case 0xdb:
			ok = ProcessDQT(data, len, &pos, jpg);
			break;
		case 0xdd:
			ok = ProcessDRI(data, len, &pos, jpg);
			break;
		case 0xe0:
		case 0xe1:
		case 0xe2:
		case 0xe3:
		case 0xe4:
		case 0xe5:
		case 0xe6:
		case 0xe7:
		case 0xe8:
		case 0xe9:
		case 0xea:
		case 0xeb:
		case 0xec:
		case 0xed:
		case 0xee:
		case 0xef:
			if (mode != JPEG_READ_TABLES) {
				ok = ProcessAPP(data, len, &pos, jpg);
			}
			break;
		case 0xfe:
			if (mode != JPEG_READ_TABLES) {
				ok = ProcessCOM(data, len, &pos, jpg);
			}
			break;
		default:
			fprintf(stderr, "Unsupported marker: %d pos=%d len=%d\n",
				marker, static_cast<int>(pos), static_cast<int>(len));
			jpg->error = JPEG_UNSUPPORTED_MARKER;
			ok = false;
			break;
		}
		if (!ok) {
			return false;
		}
		////jpg->marker_order.push_back(marker);
		if (mode == JPEG_READ_HEADER && found_sof && found_dht) {
			break;
		}
	} while (marker != 0xd9);

	if (!found_sof) {
		fprintf(stderr, "Missing SOF marker.\n");
		jpg->error = JPEG_SOF_NOT_FOUND;
		return false;
	}

	// Supplemental checks.
	if (mode == JPEG_READ_ALL) {
		if (pos < len) {
			jpg->tail_data = &data[pos];//), len - pos);
		}
		if (!FixupIndexes(jpg)) {
			return false;
		}
		if (jpg->huffman_codeLen == 0) {
			// Section B.2.4.2: "If a table has never been defined for a particular
			// destination, then when this destination is specified in a scan header,
			// the results are unpredictable."
			fprintf(stderr, "Need at least one Huffman code table.\n");
			jpg->error = JPEG_HUFFMAN_TABLE_ERROR;
			return false;
		}
		if (jpg->huffman_codeLen >= kMaxDHTMarkers) {
			fprintf(stderr, "Too many Huffman tables.\n");
			jpg->error = JPEG_HUFFMAN_TABLE_ERROR;
			return false;
		}
	}
	return true;
}

// Mimic libjpeg's heuristics to guess jpeg color space.
// Requires that the jpg has 3 components.
bool HasYCbCrColorSpace(const JPEGData* jpg) {
	bool has_Adobe_marker = false;
	uint8_t Adobe_transform = 0;

	myVector* next = jpg->app_data;
	while (next){
		mystr* s = (mystr*)(next->p);
		const uint8_t* app = s->str;
		if (app[0] == 0xe0) {
			return true;
		}
		else if (app[0] == 0xee && s->len >= 15) {
			has_Adobe_marker = true;
			Adobe_transform = app[14];
		}
		next = next->next;
	}


	//for (const std::string& app : jpg->app_data) {
	//	if (static_cast<uint8_t>(app[0]) == 0xe0) {
	//		return true;
	//	}
	//	else if (static_cast<uint8_t>(app[0]) == 0xee && app.size() >= 15) {
	//		has_Adobe_marker = true;
	//		Adobe_transform = app[14];
	//	}
	//}
	if (has_Adobe_marker) {
		return (Adobe_transform != 0);
	}
	const int cid0 = jpg->components[0].id;
	const int cid1 = jpg->components[1].id;
	const int cid2 = jpg->components[2].id;
	return (cid0 != 'R' || cid1 != 'G' || cid2 != 'B');
}

// Computes out[x] = sum{kIDCTMatrix[8*x+u]*in[u*stride]; for u in [0..7]}
void Compute1dIDCT(const coeff_t* in, const int stride, int* out) {
	int tmp0, tmp1, tmp2, tmp3, tmp4;

	tmp1 = kIDCTMatrix[0] * in[0];
	out[0] = out[1] = out[2] = out[3] = out[4] = out[5] = out[6] = out[7] = tmp1;

	int stride_ = stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[1] * tmp0;
	tmp2 = kIDCTMatrix[9] * tmp0;
	tmp3 = kIDCTMatrix[17] * tmp0;
	tmp4 = kIDCTMatrix[25] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[2] * tmp0;
	tmp2 = kIDCTMatrix[10] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] -= tmp2;
	out[3] -= tmp1;
	out[4] -= tmp1;
	out[5] -= tmp2;
	out[6] += tmp2;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[3] * tmp0;
	tmp2 = kIDCTMatrix[11] * tmp0;
	tmp3 = kIDCTMatrix[19] * tmp0;
	tmp4 = kIDCTMatrix[27] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[4] * tmp0;
	out[0] += tmp1;
	out[1] -= tmp1;
	out[2] -= tmp1;
	out[3] += tmp1;
	out[4] += tmp1;
	out[5] -= tmp1;
	out[6] -= tmp1;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[5] * tmp0;
	tmp2 = kIDCTMatrix[13] * tmp0;
	tmp3 = kIDCTMatrix[21] * tmp0;
	tmp4 = kIDCTMatrix[29] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[6] * tmp0;
	tmp2 = kIDCTMatrix[14] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] -= tmp2;
	out[3] -= tmp1;
	out[4] -= tmp1;
	out[5] -= tmp2;
	out[6] += tmp2;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_];
	tmp1 = kIDCTMatrix[7] * tmp0;
	tmp2 = kIDCTMatrix[15] * tmp0;
	tmp3 = kIDCTMatrix[23] * tmp0;
	tmp4 = kIDCTMatrix[31] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;
}
void Compute1dIDCT2(const coeff_t* in, int* in2, const int stride, int* out) {
	int tmp0, tmp1, tmp2, tmp3, tmp4;

	tmp1 = kIDCTMatrix[0] * in[0] * in2[0];
	out[0] = out[1] = out[2] = out[3] = out[4] = out[5] = out[6] = out[7] = tmp1;

	int stride_ = stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[1] * tmp0;
	tmp2 = kIDCTMatrix[9] * tmp0;
	tmp3 = kIDCTMatrix[17] * tmp0;
	tmp4 = kIDCTMatrix[25] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[2] * tmp0;
	tmp2 = kIDCTMatrix[10] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] -= tmp2;
	out[3] -= tmp1;
	out[4] -= tmp1;
	out[5] -= tmp2;
	out[6] += tmp2;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[3] * tmp0;
	tmp2 = kIDCTMatrix[11] * tmp0;
	tmp3 = kIDCTMatrix[19] * tmp0;
	tmp4 = kIDCTMatrix[27] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[4] * tmp0;
	out[0] += tmp1;
	out[1] -= tmp1;
	out[2] -= tmp1;
	out[3] += tmp1;
	out[4] += tmp1;
	out[5] -= tmp1;
	out[6] -= tmp1;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[5] * tmp0;
	tmp2 = kIDCTMatrix[13] * tmp0;
	tmp3 = kIDCTMatrix[21] * tmp0;
	tmp4 = kIDCTMatrix[29] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[6] * tmp0;
	tmp2 = kIDCTMatrix[14] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] -= tmp2;
	out[3] -= tmp1;
	out[4] -= tmp1;
	out[5] -= tmp2;
	out[6] += tmp2;
	out[7] += tmp1;

	stride_ += stride;
	tmp0 = in[stride_] * in2[stride_];
	tmp1 = kIDCTMatrix[7] * tmp0;
	tmp2 = kIDCTMatrix[15] * tmp0;
	tmp3 = kIDCTMatrix[23] * tmp0;
	tmp4 = kIDCTMatrix[31] * tmp0;
	out[0] += tmp1;
	out[1] += tmp2;
	out[2] += tmp3;
	out[3] += tmp4;
	out[4] -= tmp4;
	out[5] -= tmp3;
	out[6] -= tmp2;
	out[7] -= tmp1;
}

void ComputeBlockIDCT(const coeff_t* block, int* quant, uint8_t* out) {
	coeff_t colidcts[kDCTBlockSize];
	const int kColScale = 11;
	const int kColRound = 1 << (kColScale - 1);
	for (int x = 0; x < 8; x++) {
		int colbuf[8];
		//for (int i = 0; i < 8; i++){
		//	colbuf[i] = 0;
		//}
		Compute1dIDCT2(block + x, quant + x, 8, colbuf);
		for (int y = 0; y < 8; ++y) {
			colidcts[8 * y + x] = (colbuf[y] + kColRound) >> kColScale;
		}
	}
	const int kRowScale = 18;
	const int kRowRound = 257 << (kRowScale - 1);  // includes offset by 128
	for (int y = 0; y < 8; ++y) {
		int rowidx = 8 * y;
		int rowbuf[8];
		//for (int i = 0; i < 8; i++){
		//	rowbuf[i] = 0;
		//}
		Compute1dIDCT(&colidcts[rowidx], 1, rowbuf);
		for (int x = 0; x < 8; ++x) {
			out[rowidx + x] = max(0, min(255, (rowbuf[x] + kRowRound) >> kRowScale));
		}
	}
}

struct OutputImageComponent {
	//OutputImageComponent(int w, int h);
	void init(int w, int h)
	{
		width_ = w;
		height_ = h;
		//Reset(1, 1);
	}

	void Reset(int factor_x, int factor_y, int jpgWidth, int jpgHeight) {
		factor_x_ = factor_x;
		factor_y_ = factor_y;
		int w = jpgWidth> width_ ? width_ : jpgWidth;
		int h = jpgHeight>height_ ? height_ : jpgHeight;

		width_in_blocks_ = (w + 8 * factor_x_ - 1) / (8 * factor_x_);
		height_in_blocks_ = (h + 8 * factor_y_ - 1) / (8 * factor_y_);
		num_blocks_ = width_in_blocks_ * height_in_blocks_;
	}


	// Fills in out[] array with the floating-point precision pixel view of the
	// component.
	// REQUIRES: factor_x() == 1 and factor_y() == 1.
////void ToFloatPixels(float* out, int stride) const;

	// Sets the 8x8 coefficient block with block coordinates (block_x, block_y)
	// to block[].
	// NOTE: If the component is 2x2 subsampled, this corresponds to the 16x16
	// pixel area with upper-left corner (16 * block_x, 16 * block_y).
	// REQUIRES: block[k] % quant()[k] == 0 for each coefficient index k.

	// Requires that comp is not downsampled.
	void CopyFromJpegComponent(const JPEGComponent& comp, int* quant, uint8_t* out, int stride) {
		const size_t src_row_size = comp.width_in_blocks * kDCTBlockSize;
		//const size_t coeffs_size = width_in_blocks_ * height_in_blocks_ * kDCTBlockSize;

		// Note: coefficients are 10 bits as well, so when the three are multiplied,
		// the number is 30-bit fixed point.

		for (int block_y = 0; block_y < height_in_blocks_; block_y++) {
			const coeff_t* src_coeffs = &comp.coeffs[block_y * src_row_size];
			for (int block_x = 0; block_x < width_in_blocks_; block_x++) {

				uint8_t idct[kDCTBlockSize];
				ComputeBlockIDCT(src_coeffs, quant, idct);
				UpdatePixelsForBlock(block_x, block_y, idct, out, stride);


				src_coeffs += kDCTBlockSize;
			}
		}

	}

	void UpdatePixelsForBlock(int block_x, int block_y, const uint8_t* idct, uint8_t* out, int stride) {
		if (factor_x_ == 1 && factor_y_ == 1) {
			for (int iy = 0; iy < 8; ++iy) {
				int y = 8 * block_y + iy;
				for (int ix = 0; ix < 8; ++ix) {
					int x = 8 * block_x + ix;
					if (x < width_ && y < height_){
						int p = y * width_ + x;
						out[p << stride] = idct[8 * iy + ix];
					}
				}
			}
		}
		else if (factor_x_ == 2 && factor_y_ == 2) {
			for (int iy = 0; iy < 8; ++iy) {
				int y = (8 * block_y + iy) * 2;
				for (int ix = 0; ix < 8; ++ix) {
					int x = (8 * block_x + ix) * 2;
					uint8_t val = idct[8 * iy + ix];
					if (x < width_ && y < height_){
						int p = y * width_ + x;
						out[p << stride] = val;
					}
					if (x + 1 < width_ && y < height_){
						int p = y * width_ + x + 1;
						out[p << stride] = val;
					}
					if (x < width_ && y+1 < height_){
						int p = (y + 1) * width_ + x;
						out[p << stride] = val;
					}
					if (x + 1 < width_ && y+1 < height_){
						int p = (y + 1) * width_ + x + 1;
						out[p << stride] = val;
					}
				}
			}
		}
		else {
			fprintf(stderr,"Sampling ratio not supported: factor_x = %d factor_y = %d\n", factor_x_, factor_y_);
			//exit(1);
		}
	}

	int width_;
	int height_;
	int factor_x_;
	int factor_y_;
	int width_in_blocks_;
	int height_in_blocks_;
	int num_blocks_;
	//int quant_[kDCTBlockSize];
};


int aa();

void test(char* in, char* out){
	FILE* infile;		/* source file */
	infile = fopen(in, "rb");
	fseek(infile, 0L, SEEK_END);
	int len = ftell(infile);
	fseek(infile, 0L, SEEK_SET);

	workspaceIndex = 0;
	workspaceMaxUse = 0;
	workspace = (uint8_t*)malloc(workspaceTop);

	uint8_t* p = (uint8_t*)malloc(len);

	int canvasW = 1024;
	int canvasH = 768;

	int ret = fread(p, 1, len, infile);
	try{
		int t1 = aa();


		JPEGData* jpg = (JPEGData*)workspaceMalloc(sizeof(JPEGData));
		initJPEGData(jpg);
		ReadJpeg(p, len, JPEG_READ_ALL, jpg);

		uint8_t* rgb = (uint8_t*)malloc(canvasW * canvasH * 2);
		uint16_t* rgb16 = (uint16_t*)rgb;

		//DecodeJpegToRGB(jpg, rgb);
		//void DecodeJpegToRGB(const JPEGData* jpg, uint8_t* rgb) 
		{
			if (jpg->componentsLen == 1 ||
				(
				jpg->componentsLen == 3 && HasYCbCrColorSpace(jpg) && (jpg->Is420() || jpg->Is444())
				)
				){

				{
					uint8_t* extchannel = (uint8_t*)workspaceMalloc(canvasW * canvasH);
					OutputImageComponent* c = (OutputImageComponent*)workspaceMalloc(sizeof(OutputImageComponent));
					c->init(canvasW, canvasH);
					for (int i = 0; i < jpg->componentsLen; ++i) {
						const JPEGComponent& comp = jpg->components[i];
						int factor_x = jpg->max_h_samp_factor / comp.h_samp_factor;
						int factor_y = jpg->max_v_samp_factor / comp.v_samp_factor;
						myVector* v = jpg->quant;
						int index = 0;
						while (index < comp.quant_idx && v->next){
							v = v->next;
							index++;
						}
						JPEGQuantTable* p = (JPEGQuantTable*)v->p;
						c->Reset(factor_x, factor_y, jpg->width,jpg->height);
						if (i == 0){
							c->CopyFromJpegComponent(comp, p->values, extchannel, 0);
						}
						else if (i == 1){
							c->CopyFromJpegComponent(comp, p->values, rgb, 1);// p->values  ===   &jpg->quant[comp.quant_idx].values[0]
						}
						else{
							c->CopyFromJpegComponent(comp, p->values, rgb + 1, 1);
						}
					}

					workspaceFree(canvasW * canvasH);
					workspaceFree(sizeof(OutputImageComponent));

					int w = jpg->width> canvasW ? canvasW : jpg->width;
					int h = jpg->height>canvasH ? canvasH : jpg->height;

					for (int j = 0; j < h; j++) {
						for (int i = 0; i < w; i++) {
							//ColorTransformYCbCrToRGB(rgb16 + p, extchannel[p], rgb[p << 1], rgb[1 + (p << 1)]);
							int p = j*canvasW + i;
							int y = extchannel[p];
							int cb = rgb[p << 1];
							int cr = rgb[1 + (p << 1)];

							int r = kRangeLimitLut[384 + y + kCrToRedTable[cr]];
							int g = kRangeLimitLut[384 + y + ((kCrToGreenTable[cr] + kCbToGreenTable[cb]) >> 16)];
							int b = kRangeLimitLut[384 + y + kCbToBlueTable[cb]];

							uint16_t val = 0;
							val |= (r >> 3) << (5 + 6);
							val |= (g >> 2) << (5);
							val |= (b >> 3);
							rgb16[p] = val;
						}
					}
				}
				
			}
		}

		int t2 = aa();
		int t3 = t2 - t1;
		printf("%d",t3);

		int rgblen = canvasW * canvasH * 2;
		int w = canvasW;
		int h = canvasH;
		FILE* outfile = fopen(out, "wb");
		fwrite(&w, 4, 1, outfile);
		fwrite(&h, 4, 1, outfile);
		fwrite(rgb, 1, rgblen, outfile);
		fclose(outfile);

	}
	catch(int ex){
		printf(" error ");
	}
	fclose(infile);
	
	workspaceFree(sizeof(JPEGData));

	free(workspace);
	free(p);
	printf(in);
	printf(" workspaceMaxUse=%d\r\n", workspaceMaxUse);

}

int _tmain(int argc, _TCHAR* argv[])
{

	//test("D:\\jpeglib\\test0.jpg", "D:\\jpeglib\\test0.img");
	//test("D:\\jpeglib\\test1.jpg", "D:\\jpeglib\\test1.img");
	test("D:\\jpeglib\\test2.jpg", "D:\\jpeglib\\test2.img");//30s / 0.022ms = 1363   3Ghz   3000/1363 = 2.2Mhz equ

	//test("D:\\jpeglib\\test3.jpg", "D:\\jpeglib\\test3.img");
	//test("D:\\jpeglib\\test4.jpg", "D:\\jpeglib\\test4.img");
	//test("D:\\jpeglib\\test5.jpg", "D:\\jpeglib\\test5.img");
	//test("D:\\jpeglib\\test6.jpg", "D:\\jpeglib\\test6.img");
	//test("D:\\jpeglib\\test7.jpg", "D:\\jpeglib\\test7.img");
	//test("D:\\jpeglib\\test8.jpg", "D:\\jpeglib\\test8.img");
	//test("D:\\jpeglib\\test9.jpg", "D:\\jpeglib\\test9.img");
	//test("D:\\jpeglib\\test10.jpg", "D:\\jpeglib\\test10.img");
	//test("D:\\jpeglib\\test11.jpg", "D:\\jpeglib\\test11.img");
	//test("D:\\jpeglib\\test12.jpg", "D:\\jpeglib\\test12.img");
	//test("D:\\jpeglib\\test13.jpg", "D:\\jpeglib\\test13.img");
	//test("D:\\jpeglib\\test14.jpg", "D:\\jpeglib\\test14.img");
	//test("D:\\jpeglib\\test15.jpg", "D:\\jpeglib\\test15.img");
	//test("D:\\jpeglib\\test16.jpg", "D:\\jpeglib\\test16.img");
	//test("D:\\jpeglib\\test17.jpg", "D:\\jpeglib\\test17.img");
	//test("D:\\jpeglib\\test18.jpg", "D:\\jpeglib\\test18.img");
	//test("D:\\jpeglib\\test19.jpg", "D:\\jpeglib\\test19.img");
	//test("D:\\jpeglib\\test20.jpg", "D:\\jpeglib\\test20.img");

	getchar();
	return 0;
}

